//Sam.XIAO
#include <bits/stdc++.h>
using namespace std;

class solution {
   char *num, *bin;
   int base, k;

   //base10 to base2
   int tobin() {
      int len = strlen(num), pos = 0;
      for (int i = 0; i < len; i++) num[i] -= '0';
      while (true) {
         bool bOk = true;
         for (int i = 0; i < len; i++) {
            num[i + 1] += (num[i] % 2) * 10;
            num[i] /= 2;
            if (num[i]) bOk = false;
         }
         bin[pos++] = num[len] / 10;
         num[len] = 0;  // !!!
         if (bOk) break;
      }
      return pos;
   }

   //quick power then mod
   int quick_power() {
      int pos = 0, res = 1;
      int len = tobin();
      //for (int i = 0; i < len; i++) printf("%d%s", bin[i], i == len - 1 ? "\n" : " ");
      while (len--) {
         if (bin[pos++]) res = res * base % k;
         base = base * base % k;
      }
      return res;
   }

   ~solution() {
      if (bin) delete bin;
      if (num) delete num;
   }

  public:
   solution(char const *const num10, int base, int k) : base(base), k(k) {
      int l = strlen(num10) * (ceil(log2(10))) + 10;
      bin = new char[l];
      memset(bin, 0, l);

      l = strlen(num10) + 2;
      num = new char[l];
      memset(num, 0, l);
      memcpy(num, num10, strlen(num10));
   }

   int getans() {
      return quick_power();
   }
};

void work2() {
   int k;
   scanf("%d", &k);

   while (k--) {
      char s[300];
      memset(s, 0, sizeof(s));
      scanf("%s", s);
      solution *sln = new solution(s, 2011, 10000);
      printf("%d\n", sln->getans());
   }
}

int main() {
   work2();
   return 0;
}
